#include "uniform_grid.h"

using namespace tls;


uniform_grid::uniform_grid(const linear_aggr& aggr):mesh(aggr){
  world.l=vec3(inf,inf,inf);
  world.u=vec3(-inf,-inf,-inf);
  for(int i=0;i<mesh.faces.size();++i)
    world=world.make_union(mesh.faces[i].tri.box);
  
  vec3 extent=world.u - world.l;
  unit=extent / (real)MAXN;
  
  //fill
  for(int i=0;i<mesh.faces.size();++i){
    aabb box=mesh.faces[i].tri.box;
    int start[3],end[3];
    for(int j=0;j<3;++j){
      start[j]=pos2voxel(box.l,j);
      if(start[j]>=MAXN) --start[j];

      end[j]=pos2voxel(box.u,j);
      if(end[j]>=MAXN) --end[j];
    }

    for(int x=start[0];x<=end[0];++x)
      for(int y=start[1];y<=end[1];++y)
	for(int z=start[2];z<=end[2];++z)
	  voxels[x][y][z].push_back(&mesh.faces[i]);
  }//fill end
}

bool uniform_grid::intersect(ray& r,isect& hit)const{
  real delta[3],nextT[3];
  int out[3],step[3],pos[3];
  bool isNeg[3]={r.d.x<0, r.d.y<0, r.d.z<0};
  real T;
  real tmp=r.t;

  if(world.in(r.o)) T=0;
  else
    if(!world.intersect(r)) return false;
    else T=r.t;

  vec3 P=r.o + T*r.d;
  //set up
  for(int j=0;j<3;++j){
    pos[j]=pos2voxel(P,j);
    if(pos[j]==MAXN) --pos[j];
    if(isNeg[j]){
      delta[j]=-unit[j] / r.d[j];
      nextT[j]=T+(voxel2pos(pos[j],j) - P[j]) / r.d[j];
      step[j]=-1;
      out[j]=-1;
    }
    else{
      delta[j]=unit[j] / r.d[j];
      nextT[j]=T+(voxel2pos(pos[j]+1,j) - P[j]) / r.d[j];
      step[j]=1;
      out[j]=MAXN;
    }
  }

  //traverse
  r.t=tmp;
  bool bhit=false;
  while(1){
    int x=pos[0],y=pos[1],z=pos[2];
    for(vector<triangle*>::const_iterator i=voxels[x][y][z].begin();i!=voxels[x][y][z].end();++i)
      if((*i)->intersect(r,hit)) bhit=true;

    int bits=((nextT[0]<nextT[1]) << 2) + ((nextT[0]<nextT[2]) << 1) +
      ((nextT[1]<nextT[2]));
    const int cmpToAxis[]={2,1,2,1,2,2,0,0};
    int stepAxis=cmpToAxis[bits];

    if(r.t < nextT[stepAxis]) break;
    pos[stepAxis]+=step[stepAxis];
    if(pos[stepAxis]==out[stepAxis]) break;
    nextT[stepAxis]+=delta[stepAxis];
  }//while(1)

  return bhit;
}
    
bool uniform_grid::intersectP(ray& r)const{
  real delta[3],nextT[3];
  int out[3],step[3],pos[3];
  bool isNeg[3]={r.d.x<0, r.d.y<0, r.d.z<0};
  real T;
  real tmp=r.t;

  if(world.in(r.o)) T=0;
  else
    if(!world.intersect(r)) return false;
    else T=r.t;

  vec3 P=r.o+T*r.d;
  //set up
  for(int j=0;j<3;++j){
    pos[j]=pos2voxel(P,j);
    if(pos[j]==MAXN) --pos[j];
    if(isNeg[j]){
      delta[j]=-unit[j] / r.d[j];
      nextT[j]=T+(voxel2pos(pos[j],j) - P[j]) / r.d[j];
      step[j]=-1;
      out[j]=-1;
    }
    else{
      delta[j]=unit[j] / r.d[j];
      nextT[j]=T+(voxel2pos(pos[j]+1,j) - P[j]) / r.d[j];
      step[j]=1;
      out[j]=MAXN;
    }
  }

  //traverse
  r.t=tmp;
  isect hit;
  while(1){
    int x=pos[0],y=pos[1],z=pos[2];
    for(vector<triangle*>::const_iterator i=voxels[x][y][z].begin();i!=voxels[x][y][z].end();++i)
      if((*i)->intersect(r,hit)) return true;

    int bits=((nextT[0]<nextT[1]) << 2) + ((nextT[0]<nextT[2]) << 1) +
      ((nextT[1]<nextT[2]));
    const int cmpToAxis[]={2,1,2,1,2,2,0,0};
    int stepAxis=cmpToAxis[bits];

    if(r.t < nextT[stepAxis]) break;
    pos[stepAxis]+=step[stepAxis];
    if(pos[stepAxis]==out[stepAxis]) break;
    nextT[stepAxis]+=delta[stepAxis];
  }//while(1)

  return false;
}
